home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / tar / trees.c < prev    next >
Text File  |  1980-07-23  |  39KB  |  1,043 lines
  1. /*
  2.  The following sorce code is derived from Info-Zip 'zip' 2.01
  3.  distribution copyrighted by Mark Adler, Richard B. Wales,
  4.  Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  5. */
  6.  
  7. /*
  8.  *  trees.c is initially written by Jean-loup Gailly
  9.  *
  10.  *  This is a new version of im_ctree.c originally written by Richard B. Wales
  11.  *  for the defunct implosion method.
  12.  *
  13.  *  PURPOSE
  14.  *
  15.  *      Encode various sets of source values using variable-length
  16.  *      binary code trees.
  17.  *
  18.  *  DISCUSSION
  19.  *
  20.  *      The PKZIP "deflation" process uses several Huffman trees. The more
  21.  *      common source values are represented by shorter bit sequences.
  22.  *
  23.  *      Each code tree is stored in the ZIP file in a compressed form
  24.  *      which is itself a Huffman encoding of the lengths of
  25.  *      all the code strings (in ascending order by source values).
  26.  *      The actual code strings are reconstructed from the lengths in
  27.  *      the UNZIP process, as described in the "application note"
  28.  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  29.  *
  30.  *  REFERENCES
  31.  *
  32.  *      Lynch, Thomas J.
  33.  *          Data Compression:  Techniques and Applications, pp. 53-55.
  34.  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
  35.  *
  36.  *      Storer, James A.
  37.  *          Data Compression:  Methods and Theory, pp. 49-50.
  38.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  39.  *
  40.  *      Sedgewick, R.
  41.  *          Algorithms, p290.
  42.  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  43.  *
  44.  *  INTERFACE
  45.  *
  46.  *      int ct_init (void)
  47.  *          Allocate the match buffer and initialize the various tables.
  48.  *
  49.  *      int ct_tally(int dist, int lc);
  50.  *          Save the match info and tally the frequency counts.
  51.  *          Return true if the current block must be flushed.
  52.  *
  53.  *      long flush_block (char *buf, ulg stored_len, int eof)
  54.  *          Determine the best encoding for the current block: dynamic trees,
  55.  *          static trees or store, and output the encoded block to the zip
  56.  *          file. Returns the total compressed length for the file so far.
  57.  */
  58.  
  59. #include "modern.h"
  60. #include "zalloc.h"
  61. #include "zipdefs.h"
  62. #include "zipguts.h"
  63. #include "zippipe.h"
  64.  
  65. #define MAX_BITS 15
  66. /* All codes must not exceed MAX_BITS bits */
  67.  
  68. #define MAX_BL_BITS 7
  69. /* Bit length codes must not exceed MAX_BL_BITS bits */
  70.  
  71. #define LENGTH_CODES 29
  72. /* number of length codes, not counting the special END_BLOCK code */
  73.  
  74. #define LITERALS  256
  75. /* number of literal bytes 0..255 */
  76.  
  77. #define END_BLOCK 256
  78. /* end of block literal code */
  79.  
  80. #define L_CODES (LITERALS+1+LENGTH_CODES)
  81. /* number of Literal or Length codes, including the END_BLOCK code */
  82.  
  83. #define D_CODES   30
  84. /* number of distance codes */
  85.  
  86. #define BL_CODES  19
  87. /* number of codes used to transfer the bit lengths */
  88.  
  89.  
  90. static int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
  91.    = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
  92.  
  93. static int near extra_dbits[D_CODES] /* extra bits for each distance code */
  94.    = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
  95.  
  96. static int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
  97.    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
  98.  
  99. #define STORED_BLOCK 0
  100. #define STATIC_TREES 1
  101. #define DYN_TREES    2
  102. /* The three kinds of block type */
  103.  
  104. #ifndef LIT_BUFSIZE
  105. #  ifdef SMALL_MEM
  106. #    define LIT_BUFSIZE  0x2000
  107. #  else
  108. #  ifdef MEDIUM_MEM
  109. #    define LIT_BUFSIZE  0x4000
  110. #  else
  111. #    define LIT_BUFSIZE  0x8000
  112. #  endif
  113. #  endif
  114. #endif
  115. #define DIST_BUFSIZE  LIT_BUFSIZE
  116. /* Sizes of match buffers for literals/lengths and distances.  There are
  117.  * 4 reasons for limiting LIT_BUFSIZE to 64K:
  118.  *   - frequencies can be kept in 16 bit counters
  119.  *   - if compression is not successful for the first block, all input data is
  120.  *     still in the window so we can still emit a stored block even when input
  121.  *     comes from standard input.  (This can also be done for all blocks if
  122.  *     LIT_BUFSIZE is not greater than 32K.)
  123.  *   - if compression is not successful for a file smaller than 64K, we can
  124.  *     even emit a stored file instead of a stored block (saving 5 bytes).
  125.  *   - creating new Huffman trees less frequently may not provide fast
  126.  *     adaptation to changes in the input data statistics. (Take for
  127.  *     example a binary file with poorly compressible code followed by
  128.  *     a highly compressible string table.) Smaller buffer sizes give
  129.  *     fast adaptation but have of course the overhead of transmitting trees
  130.  *     more frequently.
  131.  *   - I can't count above 4
  132.  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  133.  * memory at the expense of compression). Some optimizations would be possible
  134.  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  135.  */
  136.  
  137. #define REP_3_6      16
  138. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  139.  
  140. #define REPZ_3_10    17
  141. /* repeat a zero length 3-10 times  (3 bits of repeat count) */
  142.  
  143. #define REPZ_11_138  18
  144. /* repeat a zero length 11-138 times  (7 bits of repeat count) */
  145.  
  146. /* Data structure describing a single value and its code string. */
  147. typedef struct ct_data {
  148.     union {
  149.         ush  freq;       /* frequency count */
  150.         ush  code;       /* bit string */
  151.     } fc;
  152.     union {
  153.         ush  dad;        /* father node in Huffman tree */
  154.         ush  len;        /* length of bit string */
  155.     } dl;
  156. } ct_data;
  157.  
  158. #define Freq fc.freq
  159. #define Code fc.code
  160. #define Dad  dl.dad
  161. #define Len  dl.len
  162.  
  163. #define HEAP_SIZE (2*L_CODES+1)
  164. /* maximum heap size */
  165.  
  166. static ct_data near dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  167. static ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */
  168.  
  169. static ct_data near static_ltree[L_CODES+2];
  170. /* The static literal tree. Since the bit lengths are imposed, there is no
  171.  * need for the L_CODES extra codes used during heap construction. However
  172.  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  173.  * below).
  174.  */
  175.  
  176. static ct_data near static_dtree[D_CODES];
  177. /* The static distance tree. (Actually a trivial tree since all codes use
  178.  * 5 bits.)
  179.  */
  180.  
  181. static ct_data near bl_tree[2*BL_CODES+1];
  182. /* Huffman tree for the bit lengths */
  183.  
  184. typedef struct tree_desc {
  185.     ct_data near *dyn_tree;      /* the dynamic tree */
  186.     ct_data near *static_tree;   /* corresponding static tree or NULL */
  187.     int     near *extra_bits;    /* extra bits for each code or NULL */
  188.     int     extra_base;          /* base index for extra_bits */
  189.     int     elems;               /* max number of elements in the tree */
  190.     int     max_length;          /* max bit length for the codes */
  191.     int     max_code;            /* largest code with non zero frequency */
  192. } tree_desc;
  193.  
  194. static tree_desc near l_desc =
  195. {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};
  196.  
  197. static tree_desc near d_desc =
  198. {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};
  199.  
  200. static tree_desc near bl_desc =
  201. {bl_tree, (ct_data near*)0, extra_blbits, 0,       BL_CODES, MAX_BL_BITS, 0};
  202.  
  203. static ush near bl_count[MAX_BITS+1];
  204. /* number of codes at each bit length for an optimal tree */
  205.  
  206. static uch near bl_order[BL_CODES]
  207.    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
  208. /* The lengths of the bit length codes are sent in order of decreasing
  209.  * probability, to avoid transmitting the lengths for unused bit length codes.
  210.  */
  211.  
  212. static int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
  213. static int heap_len;               /* number of elements in the heap */
  214. static int heap_max;               /* element of largest frequency */
  215. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  216.  * The same heap array is used to build all trees.
  217.  */
  218.  
  219. static uch near depth[2*L_CODES+1];
  220. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  221.  
  222. static uch length_code[MAX_MATCH-MIN_MATCH+1];
  223. /* length code for each normalized match length (0 == MIN_MATCH) */
  224.  
  225. static uc